package 剑指offer;

import common.TreeNode;

/**
 * @author zhangmin
 * @create 2021-11-30 9:44
 *
 * 分治算法
 */
public class day20_07_16_33 {
    /**==============================================================================================================================================
     * 剑指 Offer 07. 重建二叉树
     * 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
     * 递归：前序遍历的第一个是根，在中序遍历中找到根即可计算出左右子树的个数，然后在递归构造左右子树即可
     * */
    TreeNode build(int[] preorder,int[] inorder,int p_start,int p_end,int i_start,int i_end){
        if (p_start<0||p_end>preorder.length||i_start<0||i_end>inorder.length||p_start>p_end||i_start>i_end) return null;
        int rootNum=preorder[p_start];
        TreeNode root=new TreeNode(rootNum);
        //index记录左右子树的分割
        int index=i_start;
        while (index<=i_end&&inorder[index]!=rootNum) index++;
        int leftNum=index-i_start,rightNum=i_end-index;
        //左子树是pre中的[p_start+1,p_start+leftNum]
        root.left=build(preorder,inorder,p_start+1,p_start+leftNum,i_start,index-1);
        root.right=build(preorder,inorder,p_start+leftNum+1,p_end,index+1,i_end);
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length==0) return null;
        return build(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
    }

    /**==============================================================================================================================================
     * 剑指 Offer 16. 数值的整数次方
     * 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
     * 1、递归---超时
     * 2、快速幂：利用十进制数字 n 的二进制表示，可对快速幂进行数学化解释。
     * */
    public double myPow1(double x, int n) {
        long b=n;
        if (x==0) return 0.0;
        if (n==0) return 1.0;
        if (n<0) return 1/myPow(x, (int) -b);
        else {
            return x*myPow(x,n-1);
        }
    }

    public double myPow(double x, int n) {
        if (x==0) return 0;
        long b=n; //大数之间取负会超出
        double res=1.0;
        if (b<0){
            x=1/x;
            b=-b;
        }
        while (b>0){
            //b&1取b二进制表示的最后一位
            if ((b&1)==1) res*=x;
            x*=x;
            //去掉二进制的最后一位
            b>>=1;
        }
        return res;
    }

    /**==============================================================================================================================================
     * 剑指 Offer 33. 二叉搜索树的后序遍历序列
     * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
     * 递归：后序遍历的结果为[左子树，右子树，根]，根的值大于左子树的每个值，小于右子树的所有元素
     * */
    boolean isPostorder(int[] postorder,int start,int end){
        if (start>=end) return true;
        int root=postorder[end];
        int p=start;
        while (postorder[p]<root) p++;
        //找到了index记录右子树的第一个元素的下标，左子树为[start,index-1],右子树为[index+1,end-1]
        int index=p;
        while (postorder[p]>root)p++;
        if (p!=end) return false;
        return isPostorder(postorder,start,index-1)&&isPostorder(postorder,index,end-1);
    }
    public boolean verifyPostorder(int[] postorder) {
        if (postorder.length==0) return true;
        return isPostorder(postorder,0,postorder.length-1);
    }
}
